导读
在该论文中，作者提出了Nr-Kmeans，作为经典K均值聚类算法的一种扩张，可以在数据集中找到多个无冗余划分，即每一个对象被分配给不同子空间的不同簇。它为每一种划分同时定位最优的，任意方向的，相互正交的子空间。噪声空间的引入令其可以移除不能很好被任意一种划分表征的特征。在论文中，作者将经典K均值聚类的代价函数转换为一个迹最小化问题，再将其转换为特征值分解问题，因为迹等于特征值之和。在特殊情况下,即仅两个子空间的情况下，对矩阵作特征值分解，负的特征值相应的特征向量可将数据投影到第一个子空间，这时对应的迹最小。接着作者将一般情况$S>2$下所有子空间的组合当作特殊情况来处理，因为所有子空间是成对正交的因此对它们做优化不影响其余子空间内的代价函数。
论文地址。
ABSTRACT
高维空间中的大量对象集合通常可用多种方式聚类，比如，对象可以按照它们的形状或者它们的颜色进行聚类。每一个分组代表数据集的不同视角。无冗余聚类这一新研究领域解决了这类问题。在本文中，作者遵循这样的方法：不同的，非冗余的类K均值类簇可能存在高维空间的不同的、任意方向的子空间中。作者假设这些子空间(另外一个可选的无聚类结构的噪声空间)相互正交(两个子空间正交即两个子空间的任意两个向量正交。ps:我理解是两个子空间不共享原空间的某一维度。)该假设能够对非冗余聚类聚类问题进行特别严格的数学处理，因此是一种特别有效的算法，作者将其称为Nr-Kmeans(For non-redundant k-means)。该算法的优越性通过理论和实验两个部分的阐释。
INTRODUCTION
聚类或者找到大量对象集合的一个自然的分组深深根植于人类认知。我们的大脑一直聚类感官刺激，以识，监控和解释它们。来自认知心理学的实验表明一岁左右的儿童早已能够可靠的发现一系列物体中的类簇。他们解决图1所示的任务并没有困难。给定一些对象的图片————来自ALOI数据集，我们直觉性地将它们聚类，分别按照红色，绿色，圆地和圆柱形的聚类规则。
对于刚会走路的孩子而言，这是一个简单的任务，但它已将最先经的聚类和降维技术推到了它们的极限，出于以下两个原因：（1）图像由包含总计611个特征的高维特征向量所表征。经典的聚类算法，比如K均值由于维度诅咒问题往往会失败。稀疏高维特征空间不包含任何聚类结构。（2）有两种同样有意义的方法可以将图1中的对象分组。在数学上，有两个不同的低维子空间，每个子空间都展现出一种重要的聚类结构。在这些子空间中的类簇是相互无冗余的，也就是，每一个对象属于不同子空间中的不同簇。
受维度诅咒的启发，许多将特征选取和降维整合在一起的精心设计的算法被提出来。这些技术旨在为每一个簇定位一个子空间，在该子空间中，该簇被最好地表征。对每一个簇一个单独的子空间有助于对抗维度诅咒，但令结果解释更困难。没有可以可视化所有簇的公共子空间。因此，很难说哪些聚类是，比如，彼此最相似或者存在异常值，或者存在聚类层次结构。受该缺点的启发，[17]提出了一种技术，该技术对单个K均值聚类可以找到最好的子空间。其他一些方法聚焦于挑战(2)，也就是定位在不同的子空间中的多个非冗余类簇。允许类簇存在任意子空间中，并且允许对象被赋予给不同子空间中的不同簇，以此来建立一个更大的解决空间。现存的非冗余子空间聚类方法有以下一个到多个的缺点：要求许多输入参数，导致大量的运行时间或者产生大量难以解释的结果。
作者研究发现在不同子空间的多个K均值聚类这一挑战。基本的思想是寻找多个相互正交的子空间，使得经典K均值聚类的目标函数在所有子空间中得到优化。另外，该论文提出的技术引入了一个噪声子空间，该噪声子空间正交于其他子空间，其数据分布被假设为是单峰的。图1展示了Nr-Kmeans的结果。该算法发现相关的子空间和相应的累类簇，和比较方法相比，在一系列任务上表现更佳。该论文的贡献如下：
- 在最优子空间上的多个重要的K均值聚类。Nr-Kmeans在正交子空间上发现多个非冗余的K均值聚类。该方法为每个聚类找到根据k均值的目标函数优化聚类分离的子空间。对每一个聚类子空间，Nr-Kmeans构造最相关的基本向量。子空间之间的正交性保证发现的聚类表示提供相互非冗余信息的数据的不同视图。这些子空间适合可视化和进一步分析，因为它们揭示了一个聚类中簇之间的关系。从K均值聚类继承而来，NR-KMEANS的结果包括可解释的簇中心，正如图1所示。
- 高效。该优化算法，Nr-Kmeans，容易实现，兼容K均值的许多扩展。即使没有其他精心设计的性能优化，该算法也很快速。
- 轻量参数。Nr-Kmeans的输入仅仅是子空间数目，及每个子空间中有多少簇。
- 噪声处理。与现有的非冗余子空间聚类方法相比，Nr-Kmeans模型包括噪声子空间的思想。该噪声子空间捕获数据中所有单峰变量，其对于聚类来说并不重要。此性质有助于Nr-Kmeans优于现有方法，尤其是在高维数据上。
NON-REDUNDANT K-MEANS
在该部分，作者阐述提出的方法Nr-Kmeans。该算法的实现和补充材料可以在这里下载。
作者将他们的算法作为著名的Lloy’d算法的一种简单扩展来描述，具有交替的分配和更新步骤。然而，有可能将Nr-Kmeans和其他提出来的K均值扩展以一种简单的方法进行扩展。
表 1显示了接下来使用的必需的符号和定义。
Cost Function
在K均值算法的经典版本中，我们希望寻找到K个簇$C_i$的集合，使得欧几里得距离平方距离的和最小化。作者在Nr-Kmeans扩展了这一基本思想，通过假设数据集可以被S种不同的方法划分。每一个聚类$j$包含$k_j$个簇并且驻留在一个任意方向的子空间中，该子空间和其余$S-1$个子空间相互正交。
更进一步，作者假设存在一个正交变化矩阵$V$(样本之间的距离不变),该矩阵可以将数据空间旋转到一个所有子空间都是轴平行(axis-parallel)的变换空间中。进一步，作者使用掩子矩阵$P_j$将数据投影到相应的轴平行子空间上。因为这些子空间并不重叠，因此旋转数据空间的每个维度都专门映射到单个子空间。一个数据点$x$可以通过${P_j}^TV^Tx$被投影到$j^th$个子空间。结合这些假设，作者得到下面的损失函数，希望最小化它：
通过优化该目标函数，我们将原来空间中特征的每一线性组合赋给子空间，该子空间通过相应的聚类最佳地表示包含的结构信息。因此，我们对$S$个K均值聚类划分中每一个划分可以找到最佳子空间。
掩子矩阵$P_J \in R^{m_j \times d}$是这样建立的，如果旋转数据空间的$a$维应该被映射到子空间的$b$维，则元素$P_j[a,b]$就被设置为1，其余的元素都被设为0。为了清楚和易于解释，作者假设子空间维度可以不必在旋转空间的特征向量内相邻。然而，如果确实需要，可以使用置换矩阵将子空间在旋转空间中对齐。
作者证明该损失函数和其理论，即他们的算法从理论角度通过与具有统计独立空间的高斯混合模型的关系找到非冗余聚类。标准K均值损失函数是具有概率分布$p(x) = \prod_{i}^k \Pi_iN(\mu_i|\sigma I)$的高斯混合模型的极限。
按照相同的方法，可以很容易地证明Nr-Kmeans的代价函数可以被视为下面具有$S$个独立子空间的高斯混合模型的对数似然函数的极限($w.r.t \sigma \longrightarrow 0$):
该混合模型的统计独立分量在极限时变为Nr-Kmeans模型的正交非冗余子空间。
Optimization Algorithm
作者通过一个Lloyd’s algorithm的修改版本来优化目标函数，如Algorithm 1所示。该算法使用如下描述的更新和分配步骤直到收敛。
第一步，先使用随机正交矩阵初始化$V$。接着，初始化每一个子空间的维度$m_j$，其中$m_1 + … + m_S = d$。为了简化，作者将维度在所有子空间上平均分配。每一个子空间维度的最优值，在接下来的优化过程得到。最后但并非最不重要的，簇中心的初始化可以使用随机或者使用k-mean++设置。
分配步骤几乎和经典K均值聚类算发一样。我们将参数$V,m_j,u_{j,i}$固定住，将每一个数据点分配给相应子空间中的簇均值与该数据点的平方距离最小的簇：${|{P_j}^TV^Tx-{P_j}^TV^Tu_i|}^2$。
对于更新步骤，我们将数据点分配固定住，并且决定最优的参数值。接下的部分讨论需要的优化步骤的细节和每一步的正确性。
Estimation of the cluster centers$u_{j,i}$
我们可以通过设置相对于$u_{j,i}$的偏导数等于零来确定聚类中心的估计量（不太懂）。这一计算结果显示了人们的直觉期望：在该子空间中的聚类均值${P_j}^TV^Tu_{j,i}$只是在原始空间中分配给该簇的所有数据点的变换平均值。它可以通过下面这个著名公式来计算：$\frac{1}{|C_{j,i}|} \sum_{x \in C_{j,i}} x$。
Estimation of $V$ in the case of subspaces $S$ = 2
接下来，我们需要估计$V$的最优值。在展示一般情况下$V$的优化策略之前，我们先考虑只有两个子空间$S = 2$的特殊情况。这些结果接下来将帮助我们优化一般情况：$S > 2$。
让我们假设现在$m_i和m_2$都是固定的，是随机的正整数，并且$d = m_i + m_2$。接下来，我们假设投影矩阵$P_1$将数据向量最前面的$m$个特征投影到第一个子空间，投影矩阵$P_2$将随后的$m_2$特征投影到第二个子空间：
对该特殊情况，损失函数如下：
我们可以将该损失函数转换为一个迹最小化的问题，通过利用一个$1 \times 1-matrix$的标量和$Tr(P_2 {P_2}^TA) = Tr(A)-Tr(P_1 {P_1}^TA)$,其中$A \in R^{d \times d}$这一事实。
转换后的目标函数如下：
其中$\Sigma_{j}$是子空间$j$所有簇的分散矩阵的和：
在公式(3)中第二项对于任意$V$来说是个常数，因为迹函数的循环性质，还因为$V$是正交矩阵，因此$Tr(V^T\Sigma_2V) = Tr(\Sigma_2)$。
接下来，我们应该注意到$P_1{P_1}^T$是对角矩阵，其前$m_1$个对角元素是1，随后的$m_2$个对角元素是0。因此，如果我们将其与$V^T[\Sigma_1-\Sigma_2]V$右乘，它让$V^T[\Sigma_1-\Sigma_2]V$左上角的$m_1 \times m_1$个元素不变，让其他所有元素都为零。进一步，我们注意到迹函数产生了特征值之和(特征值之和等于迹，所以最小化特征值和也就最小化迹)。因此，对于固定但是任意的$m_1,m_2$,有可能最小化公式(2)的函数，通过放置$[\Sigma_1-\Sigma_2]$的特征向量到$V$的列，令对应最小的$m_1$个特征值的$m_1$个特征向量将数据投影到第一个$m_1$维的子空间，余下的$m_2$个特征向量将数据投影到第二个子空间。因此，我们使用$[\Sigma_1-\Sigma_2]$的特征值分解和作为$V$列向量的特征向量————对应于按升序排列的特征值。我们应该注意到$[\Sigma_1-\Sigma_2]$是对称，因此是可以正交对角化的，并且它的所有特征值都是实数。
因为我们将$V$中的向量对应于按升序排列的特征值排序并且公式(3)中的常数项并不依赖于$m_1$和$m_2$,$V$的最佳值独立于每一个子空间的维度。这一性质给了我们在每一更新步骤中额外的能力去优化关于$m_1$和$m_2$的代价。公式(2)中的代价函数仅仅通过投影矩阵$P_1,P_2$依赖于$m_1,m_2$。因为迹是特征值的和并且我们希望最小化这个和，所以我们可以仅仅最小化这个和，如果我们将$[\Sigma_1-\Sigma_2]$的所有负特征值求和。因此，我们将和负特征值对应的特征向量分配给第一个子空间，将大于零的特征值对应的特征向量分配给第二个子空间。如果特征值是零，其对代价函数无关紧要，我们可以这些特征放到任意一个子空间。
因此，对于给定$V$，我们可以优化代价函数，通过设置$m_1$为$[\Sigma_1-\Sigma_2]$负特征值的个数，$m_2 = d-m_1$。
我们应该注意到$[\Sigma_1-\Sigma_2]$的特征值也显示了其相应的特征向量和结果特征对于聚类结构的重要性。但我们将$m_1$设置为1的时候很容易看出来，我们只能使用对应于最小的特征值的特征向量将数据投影到第一个子空间的向量来最小化代价函数。因此，该特征向量对于该聚类来说是最重要的，对于$m_1 = 2$，我们同样需要和最小的两个特征值对应的特征向量来投影数据。对于第二个聚类和最大的特征值来说，该结论同样成立。因此，将$V$的列向量对应于升序的特征值来排列，意味着我们按照这些特征向量的重要性排列它们，对第一个子空间来说是降序，对第二个子空间来说是升序。
Estimation of $V$ and $m_j$ in the general case S > 2
在一般情况$S>2$优化$V$的问题并不像特殊情况$S=2$时拥有闭式解。这就是为什么我们不能通过单一特征值分解步骤来直接优化$V$的值。但是，我们可以使用这一事实，即所有子空间都是彼此成对正交的并且旋转这两个子空间的组合空间并不影响其余子空间内的代价。因此，在一般情况下优化的技巧就是考虑将旋转空间内的两个聚类的所有组合当作特殊情况$S=2$来按上小节方法来处理。一个解释的例子如图2所示。
让我们假设我们早已更新了所有的$\mu_{j,i}$，但是现在关于早已固定的参数的$V$和$m_j$还没有达到最优。我们考虑两个聚类$s$和$t$及它们对应的在旋转空间中的两个子空间$S_s$（对应图2红色块）和$S_t$(对应图2蓝色块)。我们可以使用投影矩阵$P_{s,t} = [P_s, P_t]$将整个数据集投影到组合空间$S_{s,t}$，该投影矩阵将组合空间$S_{s,t}$的前$m_s$个维度投影到$S_s$子空间，将后面的$m_t$个维度投影到$S_t$子空间。这时我们就可以将聚类$s$和$t$及它们的组合空间$S_{s,t}$当作特殊情况$S = 2$来处理，初始化这个子空间的旋转矩阵${V_{s,t}}^{< c >} = I_{m_s+m_t}$。但是，我们假设这个旋转矩阵关于公式(2)的代价函数来说不是最优的并且对于$s$和$t$的最优子空间也许是任意方向的(在图2中最优子空间$S_s$和$S_t$分别对应黄色和紫色)。但上一节讨论的结果，让我们能够找到旋转矩阵${V_{s,t}}^{< c >}$更好的值并且让我们能够调整两个子空间的维度以使代价函数最小化。接下来，我们描述子空间$S_{s,t}$中的旋转矩阵${V_{s,t}}^{< c >}$在满空间中对应的旋转矩阵${V_{s,t}}^{< f >}$:
这个满空间中的转换矩阵可以使用$V \gets V \times{V_{s,t}}^{< c >}$来更新。另外我们也需要更新$P_s,P_t$，因为$m_s,m_t$可能发生变化并且旋转空间的一些维度可能分配给其他子空间了。我们应该记住，我们希望根据它们对聚类的重要性来排序每个子空间中的特征。对每对子空间执行此过程，我们优化变换矩阵$V$和关于每个子空间的维度$m_j$ ，因此进一步最小化我们的一般代价函数。
Accelerating the general case $S>2$
上面描述的程序有一个缺点，他将整个数据集都投影到每一个组合子空间。对于大数据集来说，这样代价很大。
但我们可以规避这个问题，因为我们只需要计算每一聚类$j$在组合子空间内的分散矩阵${\Sigma_j}^{< c >}$的和。这些矩阵可以通过$V$和$P_{s,t}$在原始空间中计算的分散矩阵${\Sigma_j}^{< f >}$的和得到。我们可以轻易的预计算原始空间中的${\Sigma_j}^{< f >}$并且对于每一个组合子空间将它们转换为${\Sigma_j}^{< c >}$。因此，${V_{s,t}}^{< c >}，m_s,m_t$可以由$eig({P_{s,t}}^TV^T|{\Sigma_s}^{< f >}-{\Sigma_t}^{< f >}|VP_{s,t})$轻易决定。
Noise-Space as a Special Subspace
作者观察到聚类结果可以通过增加一个额外的包含单一簇的子空间来得到改善。作者将该子空间称为噪声空间，其余子空间为结果聚类空间。和该噪声空间有关的特征并不建立在其他聚类空间中的任何簇的结构并且在该子空间内的所有数据点的值来自相同的单峰分布或者均匀分布。因此，根据k均值聚类假设，我们通过单个聚类描述该空间。
CONCLUSION
在该论文中，作者提出了Nr-Kmeans，作为经典K均值聚类算法的一种扩张，可以在数据集中找到多个无冗余划分。它为每一种划分同时定位最优的，任意方向的，相互垂直的子空间。噪声空间的引入令其可以移除不能很好被任意一种划分表征的特征。这可以解释为数据降维步骤。Nr-Kmeans具有许多理想的特性。 最基本的非优化版本易于实现，仅使用所有线性代数框架提供的标准功能。即使在最基本的实现中，它也非常快。
此外，Nr-Kmeans可以简单的与经典k-means的许多其他扩展相结合。
方式。
未来的努力可以针对其中的子空间和簇的数量的全自动选择过程。 其他研究方向可能在于近似扩展的发展。
REFERENCES
[17] Dominik Mautz, Wei Ye, Claudia Plant, and Christian Böhm. 2017. Towards
an Optimal Subspace for K-Means. In Proceedings of the 23rd ACM SIGKDD
International Conference on Knowledge Discovery and Data Mining, Halifax, NS,
Canada, August 13 - 17, 2017. 365–373. https://doi.org/10.1145/3097983.3097989